/**
 * //给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * //
 * //
 * //
 * // 注意：
 * //
 * //
 * // 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * // 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * //
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：s = "ADOBECODEBANC", t = "ABC"
 * //输出："BANC"
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：s = "a", t = "a"
 * //输出："a"
 * //
 * //
 * // 示例 3:
 * //
 * //
 * //输入: s = "a", t = "aa"
 * //输出: ""
 * //解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * //因此没有符合条件的子字符串，返回空字符串。
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= s.length, t.length <= 10⁵
 * // s 和 t 由英文字母组成
 * //
 * //
 * //
 * //进阶：你能设计一个在
 * //o(n) 时间内解决此问题的算法吗？
 * //
 * // Related Topics 哈希表 字符串 滑动窗口 👍 2159 👎 0
 */

package com.xixi.basicAlgroithms.dualPointer;

import java.util.HashMap;
import java.util.Map;

public class ID00076MinimumWindowSubstring {
    public static void main(String[] args) {

        Solution solution = new ID00076MinimumWindowSubstring().new Solution();
        System.out.println(solution.minWindow("abc", "ac"));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            if (t.length() > s.length()) return "";


            Map<Character, Integer> sMap = new HashMap<>();
            Map<Character, Integer> tMap = new HashMap<>();

            char[] sArray = s.toCharArray();
            char[] tArray = t.toCharArray();

            String res = ""; //s的子串长度肯定都小于等于s

            int i = 0;
            int j = 0;
            //初始化
            while (j < t.length()) { //初始化两个哈希表
                Integer sCount = sMap.putIfAbsent(sArray[j], 1);
                Integer tCount = tMap.putIfAbsent(tArray[j], 1);

                if (sCount != null) {
                    sMap.put(sArray[j], ++sCount);
                }
                if (tCount != null) {
                    tMap.put(tArray[j], ++tCount);
                }
                j++;
            }


            //遍历
            while (j <= s.length() && i <= (s.length() - t.length())) {
                int childLength = j - i;
//            if(childLength < t.length()){
//                    Integer sCount = sMap.putIfAbsent(sArray[j], 1);
//                    if(sCount !=null){
//                        sMap.put(sArray[j], ++sCount);
//                    }
//                    j++;
//
//            }
                if (!containsT(sMap, tMap)) { //如果当前子串不包含t，就让j继续往右探测
                    if (j == s.length()) break;
                    Integer sCount = sMap.putIfAbsent(sArray[j], 1);
                    if (sCount != null) {
                        sMap.put(sArray[j], ++sCount);
                    }
                    j++;
                } else { //如果当前子串包含t，i开始往右，逐步缩小子串的长度,尝试找到最小子串
                    //先记录当前子串的长度，更新s
                    if (res.isEmpty() || res.length() > childLength) {
                        res = s.substring(i, j);
                    }
                    Integer sCount = sMap.get(sArray[i]);
                    sMap.put(sArray[i], --sCount); //最多减到0？
                    i++;
                }


            }

//        if(s.length() == res.length()){ //没找到
//            return "";
//        }

            return res;

        }

        public boolean containsT(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {

            for (Character tChar : tMap.keySet()) {
                Integer tInt = tMap.get(tChar);
                Integer sInt = sMap.get(tChar);
                if (sInt == null || sInt < tInt) return false; //所有t中的字母，在s中的数目必须大于等于t中的数目
            }
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}